package org.example.myleet.queue;

import org.example.myleet.Utils.Assert;

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;

public class QueueSolution {

    /**
     * 346【队列】数据流中的移动平均值
     */
    static class MovingAverage {
        private final Queue<Integer> queue;
        private BigDecimal sum;
        private final int size;
        /** Initialize your data structure here. */
        public MovingAverage(int size) {
            this.size = size;
            sum = BigDecimal.ZERO;
            queue = new LinkedList<>();
        }
        public double next(int val) {
            if (queue.size() < size) {
                queue.add(val);
                sum = sum.add(BigDecimal.valueOf(val));
            } else {
                int remove = queue.poll();
                queue.add(val);
                sum = sum.subtract(BigDecimal.valueOf(remove));
                sum = sum.add(BigDecimal.valueOf(val));
            }
            return sum.divide(BigDecimal.valueOf(queue.size()), 5, RoundingMode.HALF_UP).doubleValue();
        }
    }

    /**
     * 1670【双队列】设计前中后队列
     * 前半段和后半段分别用不同的双端队列保存，并保持前半段队列大小小于等于后半段队列大小且大小差值不超过1
     */
    static class FrontMiddleBackQueue {
        private LinkedList<Integer> q1;
        private LinkedList<Integer> q2;

        public FrontMiddleBackQueue() {
            q1 = new LinkedList<>();
            q2 = new LinkedList<>();
        }

        public void pushFront(int val) {
            q1.offerFirst(val);
            while (q1.size() > q2.size()) {
                //保持前半段队列大小小于等于后半段队列大小
                q2.offerFirst(q1.pollLast());
            }
        }

        public void pushMiddle(int val) {
            q1.offerLast(val);
            while (q1.size() > q2.size()) {
                //保持前半段队列大小小于等于后半段队列大小
                q2.offerFirst(q1.pollLast());
            }
        }

        public void pushBack(int val) {
            q2.offerLast(val);
            while (q2.size() - q1.size() > 1) {
                //保持前半段队列大小与后半段队列大小最多相差1
                q1.offerLast(q2.pollFirst());
            }
        }

        public int popFront() {
            Integer r = q1.pollFirst();
            if (null == r) r = q2.pollFirst();
            while (q2.size() - q1.size() > 1) {
                //保持前半段队列大小与后半段队列大小最多相差1
                q1.offerLast(q2.pollFirst());
            }
            if (null == r) return -1;
            return r;
        }

        public int popMiddle() {
            Integer r;
            if (q1.size() == q2.size()) {
                r = q1.pollLast();
            } else {
                r = q2.pollFirst();
            }
            while (q1.size() > q2.size()) {
                //保持前半段队列大小小于等于后半段队列大小
                q2.offerFirst(q1.pollLast());
            }
            if (null == r) return -1;
            return r;
        }

        public int popBack() {
            Integer r = q2.pollLast();
            if (null == r) r = q1.pollLast();
            while (q1.size() > q2.size()) {
                //保持前半段队列大小小于等于后半段队列大小
                q2.offerFirst(q1.pollLast());
            }
            if (null == r) return -1;
            return r;
        }
    }

    //p1893
    public boolean isCovered(int[][] ranges, int left, int right) {
        Queue<int[]> undecided = new LinkedList<>();
        //l代表未覆盖到的左边界，r代表未覆盖到的右边界
        int l = left, r = right;
        for (int[] range : ranges) {
            if (range[0] <= l) {
                if (range[1] >= l) {
                    //有区间能覆盖到l，则将l移动到这个区间右侧未覆盖到的地方
                    l = range[1] + 1;
                    continue;
                }
            }
            if (range[1] >= r) {
                if (range[0] <= r) {
                    //有区间能覆盖到r，则将r移动到这个区间左侧未覆盖到的地方
                    r = range[0] - 1;
                    continue;
                }
            }
            if (range[0] > l && range[1] < r) {
                //这个区间左右边界都没碰到，但包含在l至r区间内，先放到队列里面待用
                undecided.offer(range);
            }
        }
        //从栈里面再捞一次待确认的区间
        int len = undecided.size();
        Queue<int[]> temp = new LinkedList<>();
        while (!undecided.isEmpty()) {
            while (!undecided.isEmpty()) {
                int[] range = undecided.poll();
                if (range[0] <= l) {
                    if (range[1] >= l) {
                        //有区间能覆盖到l，则将l移动到这个区间右侧未覆盖到的地方
                        l = range[1] + 1;
                        continue;
                    }
                }
                if (range[1] >= r) {
                    if (range[0] <= r) {
                        //有区间能覆盖到r，则将r移动到这个区间左侧未覆盖到的地方
                        r = range[0] - 1;
                        continue;
                    }
                }
                //如果以上两部分都没中，说明这个区间还是不能覆盖到左右边界，先放到temp中
                temp.offer(range);
            }
            if (temp.size() == len) {
                //没有任何一个区间可以利用来缩小左右边界，放弃吧
                break;
            }
            //有区间被用过了，接着下一轮循环再继续尝试缩小左右区间
            undecided = temp;
            temp = new LinkedList<>();
            len = undecided.size();
        }
        return l > r;
    }

    //p2100
    public List<Integer> goodDaysToRobBank(int[] security, int time) {
        int n = security.length;
        List<Integer> result = new ArrayList<>(n);
        if (n < 2 * time + 1) {
            return result;
        }
        if (time < 1) {
            for (int i = time; i < n - time; ++i) {
                result.add(i);
            }
            return result;
        }
        //队列模拟，descendQueue非递增队列，ascendQueue非递减队列
        Deque<Integer> descendQueue = new LinkedList<>();
        Deque<Integer> ascendQueue = new LinkedList<>();
        int i = 0;
        while (i < n - time) {
            while (descendQueue.size() < time && i < n) {
                if (descendQueue.isEmpty()) {
                    descendQueue.offer(security[i]);
                } else {
                    if (security[i] > descendQueue.getLast()) {
                        //存在不满足非递增，从i位置重新扫描非递减元素
                        descendQueue.clear();
                        descendQueue.offer(security[i]);
                    } else {
                        descendQueue.offer(security[i]);
                    }
                }
                ++i;
            }
            if (i >= n) {
                //到达结尾
                break;
            }
            boolean found = descendQueue.size() == time && descendQueue.getLast() >= security[i];
            if (!found) {
                //存在不满足非递增情况，两个队列各退出一位，并重新进入下一轮判断
                descendQueue.removeFirst();
                if (!ascendQueue.isEmpty()) {
                    ascendQueue.removeFirst();
                }
                continue;
            }
            //候选打劫日
            int dayOfRob = i;
            ++i;
            //offset需要加入非递减队列队尾的元素位置
            int offset = i + ascendQueue.size();
            while (ascendQueue.size() < time && offset < n) {
                if (security[dayOfRob] <= security[offset]) {
                    //要求offset位置的元素必须大于等于打劫日的大小才能满足题意
                    if (ascendQueue.isEmpty()) {
                        ascendQueue.offer(security[offset]);
                    } else {
                        if (security[offset] < ascendQueue.getLast()) {
                            //新元素不满足非递减
                            found = false;
                            break;
                        } else {
                            ascendQueue.offer(security[offset]);
                        }
                    }
                } else {
                    //新元素不满足非递减
                    found = false;
                    break;
                }
                ++offset;
            }
            if (found && ascendQueue.size() == time) {
                result.add(dayOfRob);
            }
            --i;
            //非递增和非递减队列都退出最早的一个值，为下一个位置是否符合打劫日的判读做好准备
            if (!descendQueue.isEmpty()) {
                descendQueue.removeFirst();
            }
            if (!ascendQueue.isEmpty()) {
                ascendQueue.removeFirst();
            }
        }
        return result;
    }

    /**
     * 2810【双端队列】故障键盘
     */
    public String finalString(String s) {
        Deque<Character> result = new LinkedList<>();
        boolean head = true;
        for (char c : s.toCharArray()) {
            if (c == 'i') {
                head = !head;
            } else {
                if (head) result.offerLast(c);
                else result.offerFirst(c);
            }
        }
        int n = result.size();
        char[] answer = new char[n];
        for (int i = 0; i < n; ++i) {
            if (head) {
                answer[i] = result.pollFirst();
            } else {
                answer[i] = result.pollLast();
            }
        }
        return new String(answer);
    }

    public static void main(String[] args) {
        QueueSolution solution = new QueueSolution();
        Assert.isTrue("rtsng".equals(solution.finalString("string")));
    }
}
